#include <stdio.h>
#include <stdlib.h>

//top变量时刻表示栈顶元素所在位置
int top=-1;
//二叉树节点结构
typedef struct binaryTreeNode {
    int data;   //数据域
    struct binaryTreeNode * leftChild, * rightChild;    //左右孩子指针
}binaryTreeNode_t, *binaryTree;

//初始化树的函数
void createBinaryTree(binaryTree * T) {
    *T = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->data = 1;
    //根节点左孩子
    (*T)->leftChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->leftChild->leftChild = NULL;
    (*T)->leftChild->data = 2;
    (*T)->leftChild->rightChild = NULL;
    //根节点右孩子
    (*T)->rightChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->rightChild->leftChild = NULL;
    (*T)->rightChild->data = 3;
    (*T)->rightChild->rightChild = NULL;
    //根节点左孩子的左孩子
    (*T)->leftChild->leftChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->leftChild->leftChild->leftChild = NULL;
    (*T)->leftChild->leftChild->data = 4;
    (*T)->leftChild->leftChild->rightChild = NULL;
    //根节点左孩子的右孩子
    (*T)->leftChild->rightChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->leftChild->rightChild->leftChild = NULL;
    (*T)->leftChild->rightChild->data = 5;
    (*T)->leftChild->rightChild->rightChild = NULL;
    //根节点右孩子的左孩子
    (*T)->rightChild->leftChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->rightChild->leftChild->leftChild = NULL;
    (*T)->rightChild->leftChild->data = 6;
    (*T)->rightChild->leftChild->rightChild = NULL;
    //根节点右孩子的右孩子
    (*T)->rightChild->rightChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->rightChild->rightChild->leftChild = NULL;
    (*T)->rightChild->rightChild->data = 7;
    (*T)->rightChild->rightChild->rightChild = NULL;
}

//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(binaryTreeNode_t * elem) {
    printf("%d ", elem->data);
}

//后序遍历
void PostOrderTraverse(binaryTree T) {
    if(T) {
        PostOrderTraverse(T->leftChild);
        PostOrderTraverse(T->rightChild);
        displayElem(T);
    }
    //如果结点为空，返回上一层
    return;
}



int main(int argc, char * argv[]) {
    binaryTree Tree;
    createBinaryTree(&Tree);
    printf("后序遍历1: \n");
    PostOrderTraverse(Tree);
    return 0;
}